package com.jacky.二叉树;

public class 二叉树的最近公共祖先_236 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //如果当前节点为null,或者当前节点为节点p,或者节点q,就返回当前节点
        if(root == null || root == p || root == q) return root;
        //判断q和p是否在当前节点的左树上，在的话，在的返回p节点或者q节点
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        //判断q和p是否在当前节点的右树上，在的话，在的返回p节点或者q节点
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        //如果左右子树查到子查到节点都不为null,则表面p和q分别在左右子树中，（不用确定p和q,哪个在左子树，哪个在右子树）
        if(left != null && right != null) return root;
        //如果当前节点左右子树都没查到，则返回null
        if(left == null && right == null) return null;
        //左边没有查到p或者q节点，右边查到p或者q节点
        if(left == null && right != null) {
            return right;
        }
        //最后一种情况，右边没有查到p或者q节点，左边查到p或者q节点
        return left;
    }
}
